#include <bits/stdc++.h>
using namespace std;
using ll =long long;
string s;
//https://www.nowcoder.com/practice/c43a0d72d29941c1b65c857d8ac9047e?tpId=196&tqId=39317&ru=/exam/oj

// class Solution {
//     public:
//         string compressString(string s) {
//             if(s.empty()||s.size()==1)return s;
//             string rets;
//             for(int left=0,right=0;right<s.size();)
//             {
//                 while(s[right]==s[left])right++;
//                 //不相等了
//                 rets+=s[left];
//                 if(right-left>1)rets+=to_string(right-left);
//                 left=right;
//             }
//             return rets;
//         }
//     };

//topK问题，排序也可以解决
//https://ac.nowcoder.com/acm/problem/26221
// const int N=2e5+10;
// pair<ll,ll> pii[N];
// int n,k;
// bool cmp(pair<ll,ll> pii1,pair<ll,ll> pii2)
// {
//     if(pii1.second!=pii2.second)return pii1.second>pii2.second;
//     else return pii1.first<pii2.first;
// }
// int main()
// {
//     cin>>n>>k;
//     for(int i=0;i<n;i++)cin>>pii[i].first;//酸度
//     for(int i=0;i<n;i++)cin>>pii[i].second;//甜度
//     sort(pii,pii+n,cmp);
//     ll sum1=0,sum2=0;
//     for(int i=0;i<k;i++)
//     {
//         sum1+=pii[i].first;
//         sum2+=pii[i].second;
//     }
//     cout<<sum1<<" "<<sum2<<endl;
//     return 0;
// }

//https://www.nowcoder.com/practice/2820ea076d144b30806e72de5e5d4bbf?tpId=196&tqId=37561&ru=/exam/oj
//0-1背包-线性dp-根据最后一步的选择划分
class Solution 
{
public:
    int knapsack(int V, int n, vector<vector<int> >& vw) 
    {
        vector<vector<int>> dp(n+1,vector<int>(V+1,0));
        for(int i=1;i<=n;i++)
        {
            int weight=vw[i-1][0],value=vw[i-1][1];
            for(int j=1;j<=V;j++)
            {
                //物品的重量超过当前容量，不能再放入了，写入前一个的结果
                if(weight>j)dp[i][j]=dp[i-1][j];
                else //选和不选当前物品时的可以获得的最大重量
                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight]+value);
            }
        }
        return dp[n][V];
    }
};